class Solution
{
public:
    int maximumScore(vector<int> &nums, int k)
    {
        int n = nums.size();
        vector<pair<int, int>> pre, suf;
        pre.push_back({nums[k], k});
        suf.push_back({nums[k], k});
        for (int i = k - 1; i >= 0; --i)
        {
            if (nums[i] >= pre.back().first)
            {
                pre.back().second = i;
            }
            else
            {
                pre.push_back({nums[i], i});
            }
        }
        for (int i = k + 1; i < n; ++i)
        {
            if (nums[i] >= suf.back().first)
            {
                suf.back().second = i;
            }
            else
            {
                suf.push_back({nums[i], i});
            }
        }

        int result = 0;
        set<int> numSet(nums.begin(), nums.end());
        for (int minVal : numSet)
        {
            auto preIt = lower_bound(pre.rbegin(), pre.rend(), minVal, [](auto &p, auto &val)
                                     { return p.first < val; });

            auto sufIt = lower_bound(suf.rbegin(), suf.rend(), minVal, [](auto &p, auto &val)
                                     { return p.first < val; });

            if (preIt == pre.rend() || sufIt == suf.rend())
            {
                continue;
            }
            auto [preMin, i] = *preIt;
            auto [sufMin, j] = *sufIt;

            int minMinVal = min(preMin, sufMin);

            result = max(result, minMinVal * (j - i + 1));
        }
        return result;
    }
};